//
// Created by bleedingfight on 2020/6/30.
//
#include "maxProductCutting.h"

#include <iostream>
int maxProductCutting(int n) {
  if (n <= 3) return n - 1;
  int nums = n / 3;
  int res = n % 3;
  if (res == 0)
    return pow(3, nums);
  else if (res == 1)
    return pow(3, nums - 1) * 4;
  else
    return 2 * pow(3, nums);
}

int maxProductCutting1(int n, std::vector<int> &cache) {
  if (n <= 4) return n;
  int result = n;
  for (int i = 1; i <= n / 2; i++) {
    if (cache[n - i] == 0) cache[n - i] = maxProductCutting1(n - i, cache);  //
    if (cache[i] == 0) cache[i] = maxProductCutting1(i, cache);
    result = std::max(result, cache[i] * cache[n - i]);
  }
  return result;
}

int maxProductCutting1(int n) {
  if (n <= 3)
    return n - 1;
  else {
    std::vector<int> cache = std::vector<int>(n, 0);
    return maxProductCutting1(n, cache);
  }
}
int maxProductCutting2(int n) {
  if (n == 2) return 1;
  int result = -1;
  for (int i = 1; i < n; i++)
    result = std::max(result,
                      std::max(i * (maxProductCutting2(n - i)), i * (n - i)));
  return result;
}
int maxProductCutting3(int n, std::vector<int> &cache) {
  if (n <= 3) return n - 1;
  int result = -1;
  std::vector<int> mid_result = std::vector<int>(4, 0);
  for (int i = 1; i <= n / 2; i++) {
    if (cache[i] == -1) cache[i] = maxProductCutting3(i, cache);
    if (cache[n - i] == -1) cache[n - i] = maxProductCutting3(n - i, cache);

    //        std::cout<<"n="<<n<<" x:"<<i<<" n-x="<<n-i<<"
    //        x*(n-x)="<<i*(n-i)<<" f["<<i<<"]="<<cache[i]<<"
    //        f["<<n-i<<"]="<<cache[n-i]<<" Max
    //        result:"<<std::max(cache[i]*(cache[n-i]),i*(n-i))<<"\n";
    mid_result[0] = cache[i] * (cache[n - i]);
    mid_result[1] = cache[i] * (n - i);
    mid_result[2] = i * (cache[n - i]);
    mid_result[3] = i * (n - i);
    //        std::cout<<"f(x)*f(n-x) = "<<mid_result[0]<<" f(x)*(n-x) =
    //        "<<mid_result[1]<<" x*f(x) = "<<mid_result[2]<<" i*(n-i) =
    //        "<<mid_result[3]<<"\n";
    result = std::max(result,
                      *std::max_element(mid_result.begin(), mid_result.end()));
  }
  return result;
}
int maxProductCutting3(int n) {
  std::vector<int> cache = std::vector<int>(n, -1);
  return maxProductCutting3(n, cache);
}
